/**
 * Created with IntelliJ IDEA.
 * Description:
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。
 * 如果链表无环，则返回 null。
 * User: xwl
 */

class ListNode9 {
    int val;
    ListNode9 next;
    ListNode9(int x) {
        val = x;
        next = null;
    }
}

public class Test11 {
    public ListNode9 detectCycle(ListNode9 head) {
        // 设快慢指针
        ListNode9 fast = head;
        ListNode9 slow = head;
        // 设起点到入口、环、以及相遇点到入口的长度分别为x，c，
        // 则 2 * (x + (c - y)) = x + c + (c - y)
        // 即 x = y

        // 使fast指向相遇节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 判断是否有环
        if (fast == null || fast.next ==null) {
            return null;
        }
        // 找入口点
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}